package 剑指Offer1;
/*
    如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，
    因此往下查找不可能找到目标值，往左查找可能找到目标值。
    如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，
    因此往左查找不可能找到目标值，往下查找可能找到目标值。

 */
public class _14二维数组中的查找 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length; //行
        int cols = matrix[0].length; //列

        //从第一行的右上角开始
        int row = 0;
        int col = cols - 1;
        while(row<rows && col >= 0){
            int num = matrix[row][col];
            if(num == target){
                return true;
            }else if(num > target){ //当前大于目标值
                col--;
            }else{ //当前小于目标值
                row++;
            }
        }
        return false;
    }
}
